/**
 * 
 */
package name.yzhu.wordsearch;

import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;

/**
 * a simple trie tree implement
 * @author yhzhu
 *
 */
public class TrieTree {
	public static final char MIN_CHAR = 'A';
	
    private TrieNode root = null;
    /**
     * the trie tree depth , i think the depth should be the max length word
     */
    private int depth = 0;
    
	public TrieNode getRoot() {
		return root;
	}

	/**
	 * add a word to trie tree , and every letter can take a data. so the word length must need to be equal the data length<br>
	 * <b>Note:</b> a exception <code>IllegalArgumentException</code> will be throw if the first letter is not same as the root 
	 * @param word 
	 * @param data
	 */
	public void addWord(String word, Object[] data){
		if (word == null || word.trim().equals(""))
			throw new NullPointerException("word is null");
		if (null != data && data.length != word.length())
			throw new IllegalArgumentException("word length must need to be equal the data length");
		
		int index=0;
		if (null == root){
			 if (null != data)
		         root = new TrieNode(word.charAt(0), data[0]);	
			 else
		         root = new TrieNode(word.charAt(0), null);	
			 index = 1;
		}
		if (root.getChar() != word.charAt(0))
			throw new IllegalRootException("the root of this word is different with this trie tree, please check");
		else
			index = 1;
		
		TrieNode node = root;
		for (; index<word.length(); index++){
		   char c = word.charAt(index);
		   if (null != data)
		       node = node.addChild(c, data[index]);
		   else
			   node = node.addChild(c, null);
		}
		if (word.length() > depth)
			depth = word.length();
	}
	/**
	 * check if there is the word in the tire and then return the data in the each node  
	 * @param word
	 * @return  
	 */
	public Object[] get(String word){
		if (word == null || word.trim().equals("") || word.length() > depth)
			return null;
		Object[] data = new Object[word.length()];
		if (null == root && root.getChar() != word.charAt(0))
			return null;
		data[0] = root.getData();
		TrieNode node = root;
		for (int i=1; i<word.length(); i++){
		   char c = word.charAt(i);
		   node = node.getChild(c);
		   if (null == node)
			   return null;
		   data[i] = node.getData();
		}
		if (node.getChildCount() == 0)
		    return data;
		else
			return null;
	}
	/**
	 * get all words
	 * @return
	 */
	public List<String> listAllWords(){
		List<String> allWords = new LinkedList<String>();
		listAllWords(root, String.valueOf(root.getChar()), allWords);
		
		return allWords;
	}
	
	private void listAllWords(TrieNode node, String segment, List<String> allWords) {
		if (node.getChildCount() == 0)
			return;
		
		TrieNode[] childrent = node.getChildren();
		for (int i=0; i<childrent.length; i++){
			TrieNode child = childrent[i];
			if (null != child){
			    String word = segment+(char)(i+MIN_CHAR);
				if (child.getChildCount() == 0){
				    allWords.add(word);
				}
				else {
					listAllWords(child, word, allWords);
				}
			}
		}
	}

	@Override
	public String toString() {
		return "TrieTree [root=" + root + ", depth=" + depth + "]";
	}


	/**
	 * trie tree node 
	 * @author yhzhu
	 *
	 */
	static class TrieNode{
		/**
		 * we just process A-Z and a-z
		 */
		private static final int MAX_NODE_LEN = 58;
		private char letter = 0;
		private Object data = null;
		int childCount = 0;
		private TrieNode[] children = new TrieNode[MAX_NODE_LEN];
		
		public TrieNode(char c, Object data){
			this.letter = c;
			this.data = data;
			for(int i=0; i<MAX_NODE_LEN; i++)
				children[i] = null;
		}
		/**
		 * add a letter with data to the child node
		 * @param c     a letter
		 * @param data   
		 * @return  return the new node
		 */
		public TrieNode addChild(char c, Object data){
			int idx = c - MIN_CHAR;
			if (null == children[idx]){
				children[idx] = new TrieNode(c, data);
				childCount++;
			}
			return children[idx];
		}
		/**
		 * get a child node according with a letter
		 * @param c
		 * @return
		 */
		public TrieNode getChild(char c){
			int idx = c - MIN_CHAR;
			return children[idx];
		}
		/**
		 * the numbers of child node 
		 * @return
		 */
		public int getChildCount(){
			return childCount;					
		}
		
		public char getChar() {
			return letter;
		}

		public void setChar(char c) {
			this.letter = c;
		}

		public TrieNode[] getChildren() {
			return children;
		}

		public void setChildren(TrieNode[] children) {
			this.children = children;
		}

		public Object getData() {
			return data;
		}

		public void setData(Object data) {
			this.data = data;
		}

		@Override
		public int hashCode() {
			final int prime = 31;
			int result = 1;
			result = prime * result + letter;
			return result;
		}
		/**
		 * for now, we just need to be compare the letter
		 */
		@Override
		public boolean equals(Object obj) {
			if (this == obj)
				return true;
			if (obj == null)
				return false;
			if (getClass() != obj.getClass())
				return false;
			TrieNode other = (TrieNode) obj;
			if (letter != other.letter)
				return false;
			return true;
		}
		@Override
		public String toString() {
			return "TrieNode [letter=" + letter + ", data=" + data + ", childCount="
					+ childCount + ", children=" + Arrays.toString(children)
					+ "]";
		}		
		
	}
	/**
	 * this exception should be throw if the first letter in the word is not same as the root of the tire tree when add a word to trie tree
	 * @author yhzhu
	 *
	 */
	static public class IllegalRootException extends IllegalArgumentException{

		/**
		 * 
		 */
		private static final long serialVersionUID = 6844782686852460438L;

		public IllegalRootException() {
			super();
		}

		public IllegalRootException(String message, Throwable cause) {
			super(message, cause);
		}

		public IllegalRootException(String s) {
			super(s);
		}

		public IllegalRootException(Throwable cause) {
			super(cause);
		}
		
	}
}
